#include <iostream>
#include <vector>
#include <string>

using namespace std;

class Solution {
public:
    bool isMatch(int x, int y,vector<vector<char> > &board, char c,bool **visited)
    {
        if( x < 0 || y<0 || x>=board.size() || y>=board[x].size() ) return false;
        else
            return (board[x][y] == c) && (!visited[x][y]);
    }
    
    bool exist(int x,int y,vector<vector<char> > &board, string word, bool **visited)
    {
        visited[x][y] = true;
        bool ret0 = false, ret1 = false, ret2 = false, ret3=false;
        
        if(word.length() == 0) return true;
        
        if( isMatch(x,y-1,board,word[0],visited) )
        {
            ret0 = exist(x,y-1,board,word.substr(1,word.length()-1),visited);
        }
        
        if( isMatch(x,y+1,board,word[0],visited) )
        {
            ret1 = exist(x,y+1,board,word.substr(1,word.length()-1),visited);
        }
        
        if( isMatch(x-1,y,board,word[0],visited) )
        {
            ret2 = exist(x-1,y,board,word.substr(1,word.length()-1),visited);
        }
        
        if( isMatch(x+1,y,board,word[0],visited) )
        {
            ret3 = exist(x+1,y,board,word.substr(1,word.length()-1),visited);
        }
        
        if(ret0 || ret1 || ret2 || ret3)
        {
            return true;
        }
        else
        {
            visited[x][y] = false;
            return false;
        }
        
    }
    bool exist(vector<vector<char> > &board, string word) {
        int X = board.size();
        
        for( int i=0; i<X; i++)
        {
            int Y = board[i].size();
            for(int j=0; j<Y ; j++ )
            {                
                if( word[0] == board[i][j] )
                {
                    bool visited[X+1][Y+1];
                    
                    if( exist(i,j,board,word.substr(1,word.length()-1), (bool**) visited) )
                    {
                        return true;
                    }
                }
            }
        }
        
        return false;
    }
};


int main(int argc, char *argv[])
{
   Solution s;
   vector<vector<char> > board;
   string word = "ab";

   vector<char> line;
   line.push_back('a');

   board.push_back(line);

   cout<< s.exist(board,word) <<endl;
}
